package com.yeban.base.day04.homework;

import java.util.Arrays;
import java.util.Scanner;

public class SortBetter02 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("请输入需要排序数组的个数n：");
        int n = sc.nextInt();
        System.out.print("请输入需要排序的数组：");
        int[] arr1 = new int[n];
        for (int i = 0; i < n; i++) {
            arr1[i] = sc.nextInt();
        }
        int[] arr2 = Arrays.copyOf(arr1, n);

        System.out.println("--------冒泡排序优化前--------");
        // 冒泡排序
        // 记录次数
        int count1 = 0;
        //趟数
        for (int i = 0; i < n - 1; i++) {
            //次数/趟
            for (int j = 0; j < n - i - 1; j++) {
                if (arr1[j] > arr1[j + 1]) {
                    int temp = arr1[j];
                    arr1[j] = arr1[j + 1];
                    arr1[j + 1] = temp;
                }
                count1++;
            }
        }
        System.out.println("一共进行了：" + count1 + "次比较！");
        System.out.println(Arrays.toString(arr1));

        System.out.println("\n--------冒泡排序优化1--------");
        // 冒泡排序优化
        // count2记录次数
        int count2 = 0;
        int left = 0;
        int right = n - 1;
        boolean swapped = true;
        while (swapped) {
            swapped = false;
            // 从左到右
            for (int j = left; j < right; j++) {
                if (arr2[j] > arr2[j + 1]) {
                    int temp1 = arr2[j];
                    arr2[j] = arr2[j + 1];
                    arr2[j + 1] = temp1;
                    swapped = true;
                }
                count2++;
            }
            right--;
            // 从右到左
            for (int k = right; k > left; k--) {
                if (arr2[k] < arr2[k - 1]) {
                    int temp2 = arr2[k];
                    arr2[k] = arr2[k - 1];
                    arr2[k - 1] = temp2;
                    swapped = true;
                }
                count2++;
            }
            left++;
        }
        System.out.println("一共进行了：" + count2 + "次比较！");
        System.out.println(Arrays.toString(arr2));
    }
}